package leetcode.editor.cn.dsa26_unionfind;
//给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
// 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
// 此外，你可以假设该网格的四条边均被水包围。
//
// 示例 1：
//输入：grid = [
//  ["1","1","1","1","0"],
//  ["1","1","0","1","0"],
//  ["1","1","0","0","0"],
//  ["0","0","0","0","0"]
//]
//输出：1
//
// 示例 2： 
//输入：grid = [
//  ["1","1","0","0","0"],
//  ["1","1","0","0","0"],
//  ["0","0","1","0","0"],
//  ["0","0","0","1","1"]
//]
//输出：3
//
// 提示： 
// m == grid.length
// n == grid[i].length 
// 1 <= m, n <= 300 
// grid[i][j] 的值为 '0' 或 '1' 
// 
// Related Topics 深度优先搜索 广度优先搜索 并查集 
// 👍 928 👎 0

import java.util.LinkedList;
import java.util.Queue;

public class NumberOfIslands200 {
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 广度优先搜索
         * @param grid
         * @return
         */
        public int numIslands(char[][] grid) {
            // 二维网格的长和宽
            int m = grid.length, n = grid[0].length;
            // 以当前节点为坐标中心，分别向上下左右四个方向查找邻接点
            int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
            int res = 0;
            Queue<int[]> queue = new LinkedList<>();
            // 1.遍历二维网格，查找每个陆地（1）节点
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == '1') { // 陆地节点
                        // 2.将该节点存入队列，然后将该陆地标记为“水”
                        queue.offer(new int[]{i, j});
                        grid[i][j] = '0';
                        // 3.将节点出队，使用广度优先搜索扩展每个连通的陆地节点，并作上述相同操作
                        while (!queue.isEmpty()) { // 逐个扩展邻接点
                            int size = queue.size();
                            for (int k = 0; k < size; k++) {
                                int[] cell = queue.poll();
                                int row = cell[0], column = cell[1];
                                for (int[] dir : dirs) { // 分别朝节点的四个方向移动
                                    int newRow = row + dir[0], newColumn = column + dir[1];
                                    // 将相连的陆地节点入队并标记为“水”
                                    if (newRow >= 0 && newRow < m && newColumn >= 0 && newColumn < n
                                            && grid[newRow][newColumn] == '1') {
                                        queue.offer(new int[]{newRow, newColumn});
                                        grid[newRow][newColumn] = '0';
                                    }
                                }
                            }
                        }
                        // 4.每完成一次广度优先搜索，岛屿数量加 1
                        res++;
                    }
                }
            }
            return res;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}